%
%  Rapport de soutenance 1 // OCRe - HUGE Software
%
%  Created by Alexandre Testu on 2008-02-01.
%  Copyright (c) 2008 Epita. All rights reserved.
%
\documentclass[]{report}

% Use utf-8 encoding for foreign characters
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}

% Setup for fullpage use
\usepackage{fullpage}


\usepackage{fancyhdr}
% Multipart figures
%\usepackage{subfigure}
% Surround parts of graphics with box
\usepackage{boxedminipage}

% Package for including code in the document
\usepackage{listings}

% If you want to generate a toc for each chapter (use with book)
\usepackage{minitoc}

% This is now the recommended way for checking for PDFLaTeX:
\usepackage{ifpdf}
\ifpdf
\usepackage[pdftex]{graphicx} \else
\usepackage{graphicx} \fi
\title{OCRe}
\author{ \textsc{Huge} Software \\
\\
\\
Premi\`ere Soutenance \\
\\
\\
\textsc{Rapport}}

\date{}

\begin{document}

\ifpdf \DeclareGraphicsExtensions{.pdf, .jpg, .tif} \else \DeclareGraphicsExtensions{.eps, .jpg} \fi

\maketitle

\pagebreak

\tableofcontents
\pagebreak

\chapter{Introduction}
L'ann\'ee derni\`ere, vous avez \'et\'e nombreux (surtout parmi les membres de nos familles respectives) \`a acclamer le jeu video Objectif:Mars. Les poutreurs de l'espace revienne presque au complet pour mettre une deuxi\`eme couche. Cette ann\'ee, ceux qui se pr\'enomment d\'esormais HUGE (Huge Union of Gorgeous Earthborn) ont d\'ecid\'e de d\'evelopper un OCR, un logiciel de reconnaissance de caract\`eres\ldots
Here we go again\footnote{C'est reparti pour un tour! (mais \c ca fait plus style en anglais, non?}.  

\part{Pr\'eparatifs}

% (fold)
\label{prt:preparatifs}

\chapter{Gen\`ese} % (fold)
\label{cha:genese}
	\section{Naissance du groupe} % (fold)
	\label{sec:naissance_du_groupe}
		Au commencement, il y avait quatre geeks. Trois rescap\'es de l'aventure Objectif:Mars trois ``poutreurs de l'espace'', c'est \`a dire Dimitri Georgoulis, Pierre Guilbert et Alexandre Testu ainsi qu'une nouvelle recrue, le sieur Thomas A\"it-taleb. Nous sommes tous des amis proches, et nous pensons que c'est ce qui nous diff\'erencie de beaucoup d'autres groupes: nous sommes soud\'es. Les diff\'erends qu'il peut y avoir au sein du groupe se r\`egle d'un claquement de doigt, et les choix que l'\'equipe a eu \`a faire ont toujours \'etait fait \`a l'unanimit\'e.
		\sub{\textsc{Huge}?, OCRe?} % (fold)
		\label{par:huge_ocre_}
			Pourquoi \textsc{Huge}? Nous m\^eme avons du mal \`a l'expliquer. L'expression remonte \`a l'ultime ``coding week'' de sup, durant laquelle ``Huge!'' est devenu une sorte de signe de ralliement. Tout n'\'etait que hugeitude \`a cette \'epoque.
			Pourquoi OCRe? Les trois premi\`eres lettres sont \'evidentes, et la troisi\`eme n'est autre que le ``e'' d'Epita. De plus, OCRe est plus facile \`a prononcer qu'``OCR''.
		% paragraph huge?_ocre_ (end)
	% section naissance_du_groupe (end)

	\section{Choix du sujet} % (fold)
	\label{sec:choix_du_sujet}
		Le fait de choisir de r\'ealiser un OCR est apparu comme une \'evidence pour tous les membres du groupe. Nous avons d\'ej\`a fait de la 3D l'ann\'ee derni\`ere, et le fait de d\'evelopper un logiciel de \emph{reconaissance d'\'ecriture} nous fascine tous les quatre.
	% section choix_du_sujet (end)
% chapter genese (end)

\chapter{Organisation} % (fold)
\label{cha:organisation}
	\section{R\'epartition des t\^aches} % (fold)
	\label{sec:r'epartition_des_t^aches}
		Comme pour notre projet de SUP, nous comptons travailler un maximum ensemble
		\subsection{Alexandre Testu} % (fold)
		\label{sub:alexandre_testu}
			En tant que chef du projet, je r\'edigerai les rapports. Je compte aussi m'occuper du site web. Nous savons tous que ces ta\^ches sont tr\`es secondaires, je compte donc m'occuper aussi du d\'eveloppement de l'interface ainsi que de la reconnaissance des caract\`eres avec Dimitri.
		% subsection alexandre_testu (end)
		\subsection{Dimitri Georgoulis} % (fold)
		\label{sub:dimitri_georgoulis}
		
		% subsection dimitri_georgoulis (end)
		\subsection{Thomas A\"it-Taleb} % (fold)
		\label{sub:thomas_a"it_taleb}
      Sur ce projet, je serais en charge de la partie ``Analyse de l'image et extraction des caractères''. Je m'occuperais ainsi de la détection des blocs, des lignes et de l'extraction des caractères. Je me chargerais enfin de détecter la mise en forme du document.
		% subsection thomas_a"it_taleb (end)
		\subsection{Pierre Guilbert} % (fold)
		\label{sub:pierre_guilbert}
		
		% subsection pierre_guilbert (end)
	% section r'epartition_des_t^aches (end)
	
	\section{Applications utilis\'ees} % (fold)
	\label{sec:applications_utilis'ees}
		\subsection{En ligne} % (fold)
		\label{sub:en_ligne}
			\paragraph{Basecamp\\} % (fold)
			\label{par:basecamp}
			Basecamp\footnote{\emph{http://www.basecamphq.com/}} est une application web de gestion de projet. Elle est développ\'e en Ruby on Rails par une start up bas\'ee \`a Chicago, 37Signals. Cette application est tr\`es intuitive, elle nous a beacoup aid\'e \`a collaborer de mani\`ere plus efficace que pendant le projet de Sup. Basecamp a \'et\'e recommand\'ee par le Wall Street Journal, Time, Business 2.0 ou encore BusinessWeek.
			% paragraph basecamp (end)
			\paragraph{Bubbl.us\\} % (fold)
			\label{par:bubbl_us}
			Il s'agit d'un logiciel de \emph{brainstorming} en Flash. Nous l'avons utilis\'e pour mieux visualiser la strusture qu'allait prendre notre OCR. La structure obtenue est visible en annexe. %ANNEXE
			% paragraph bubbl_us (end)
			% subsection en_ligne (end)
		\subsection{Hors ligne} % (fold)
		\label{sub:hors_ligne}
			\paragraph{Emacs\\} % (fold)
			\label{par:emacs}
				C'\'etait soit \c ca soit Vi\ldots
			% paragraph emacs (end)
			\paragraph{TextMate\\} % (fold)
			\label{par:textmate}
				TextMate est le meilleur \'editeur de texte disponible sur Mac (oui, un troll se cache dans cette phrase). Plus s\'erieusement, le Mac \emph{user} du groupe, Alexandre Testu, celui qui r\'edige ce rapport \`a la troisi\`eme personne appr\'ecie l'auto-compl\'etion en \LaTeX qu'offre TextMate.
			% paragraph textmate (end)
			\paragraph{CSSEdit} % (fold)
			\label{par:cssedit}
			CSSEdit est une petite merveille qui nous est offerte (enfin plut\^ot vendue) par Macrabbits. Pour faire court, c'est un \'editeur de texte optimis\'e pour le CSS.
			% paragraph cssedit (end)
			\paragraph{Subversion\\} % (fold)
			\label{par:subversion}
				Nous avons enregistr\'e OCRe sur Google Code\footnote{\emph{http://code.google.com/p/ocre}}. Pourquoi pas Sourceforge ou autre? Google Code offre tout d'abord une interface bien plus agr\'eable, il n'y a pas de publicit\'es qui prennent un tiers de la page comme sur Sourceforge. De plus, nous avons un Wiki \`a notre disposition. Google Code nous est donc apparu comme le meilleur choix pour nous comme pour nos futurs utilisateurs.
			% paragraph subversion (end)
			\paragraph{Glade} % (fold)
				Glade est un logiciel qui facilite le d\'eveloppement d'interface en Gtk. Pour plus de d\'etail, se r\'ef\'erer \`a %REF
			\label{par:glade}
			% paragraph glade (end)
		% subsection hors_ligne (end)
	% section applications_utilis'ees (end)
% chapter organisation (end)

% part preparatifs (end)




\part{Ce qu'on a fait} % (fold)
\label{prt:ce_qu_on_a_fait}

% A VERFIER (wavs)

  \chapter{Repr\'esentation des images} % (fold)
	\label{cha:repr'esentation_des_images}


    \section{Niveaux de repr\'esentation des images} % (fold)
    \label{sec:niveaux_de_repr'esentation_des_images}
  		Il existe de nombreuses manières de représenter les images en traitement numérique. On ordonne ces représentations selon une échelle d'abstraction. On distingue alors quatre principaux niveaux de représentation qui s'échelonnent du signal pour le moins abstrait jusqu'aux modèles relationnels constituant un haut niveau d'abstraction.

      En ce qui concerne le plus bas niveau d'abstraction, il y a la représentation ``images iconiques'', à savoir la représentation qui contient les données graphiques originales. Cette représentation est notamment utilisée durant le prétraitement de l'image (concernant le redressement, le débruitage ou encore le seuillage).

      Le second niveau d'abstraction est celui qui consiste à segmenter les images. Formées de différentes parties représentant des groupes de pixels agglutinés, l'image est ainsi segmentée afin de dégager des formes (ou objets) en particulier pour les traiter par la suite.

      La représentation géométrique constitue le troisième niveau de représentation. Les images sont ainsi caractérisées selon des données de forme 2D ou 3D. Cette représentation est utilisée notamment pour les simulations d'éclairage par exemple en CAO (Conception Assistée par Ordinateur).

      Enfin au plus haut niveau de l'échelle d'abstraction, on trouve les modèles relationnels qui permettent de traiter plus efficacement les données en les organisant par exemple sous la forme de réseaux sémantiques [Nilsson, 1982]. Les modèles relationnels consistent comme leurs noms l'indiquent, à mettre en relation plusieurs éléments de l'image afin de mieux comprendre et de mieux percer la signification de celle-ci.

    % section niveaux_de_repr'esentation_des_images (end)

    \section{Structures de donn\'ees images} % (fold)
    \label{sec:structures_de_donn'ees_images}
      Afin de représenter les images selon les précédents niveaux d'abstraction, nous avons besoin de structures contenant les données de l'image et implémentables en mémoire. On distingue parmi celles-ci deux grands types de structures. D'un côté, il y a les structures traditionnelles, consituées des matrices, des chaines ainsi que des structures topologiques et relationnelles. De l'autre côté, se trouvent les structures hiérarchiques telles que les pyramides et les arbres quaternaires.

      Certainement les plus connues et les plus communes, les matrices sont un moyen simple et efficace de représenter des images. Elles constituent une représentation bas-niveau des données graphiques. Chaque élément de la matrice représente un entier correspondant à la luminosité ou encore les trois composantes de couleurs RGB (ou une autre propriété élémentaire de l'image) d'un pixel (pour PICTure ELement). Le pixel dont les coordonnées seront (x,y) correspondra à l'élément (x,y) de la matrice,plus précisement à l'intersection de la ligne x et de la colonne y. Cette représentation sous forme de matrices implique certaines relations spatiales, notamment celles du voisinage, qui s'avère utile pour certains traitements de l'image. Les images binaires, les images constituées de plusieurs bandes spectrales (i.e. (Alpha) Rouge Vert Bleu) ainsi que les structures hiérarchiques constituent des exemples spécifiques d'images représentées à l'aide de matrices.


      Au stade actuel d'avancement du projet, nous représentons les images grâce aux matrices, notamment pour le prétraitement de l'image. En ce qui concerne la partie extraction des lignes et des caractères, nous avons décidé de les représenter par le biais d'une matrice binaire (0 pour un pixel blanc, 1 pour un pixel noir), décrite dans la structure \verb!s_binary_image!.

      \begin{verbatim}
				struct s_binary_image
        {
          char *name;
          int width;
          int height;
          int **data;  /* Matrix of binary integer */
          int *hproj;  /* Horizontal projection vector */
        };
			\end{verbatim}

      D'autres structures traditionnelles d'images existent. Les chaines sont un autre moyen de représenter les données graphiques. Le principe consiste à décrire les bords de l'objet que l'on veut représenter. Le contour est défini par la coordonnée de son pixel de référence et la séquence de symboles correspondant à l'orientation du pixel suivant. Chaque élément de la chaine correspond à un symbole basique de l'image, en somme un pixel. Les chaines codes ou Freeman codes [Freeman,1961] sont utilisées pour les données représentant des séquences de symboles. Côté implémentation, les chaines peuvent être représentées par un vecteur de préférence une liste chainée. Voici un exemple de chaines codes permettant de représenter le chiffre ``2''.

      % Insertion image: chaincodes.jpg


      Il est également possible de représenter plus abstraitement les images par des structures topologiques, telles que des graphes. Ces structures sont constituées d'un ensemble d'éléments et leurs relations, à savoir respectivement les sommets et les arcs du graphe. Ces graphes peuvent bien entendu être valués par un poids. Pour représenter des images, on se sert d'un graphe de régions d'adjacence où les sommets sont des régions de l'image et les arcs sont les bords, à savoir les relations de voisinage. Le graphe de régions d'adjacence est créé à partir d'une matrice contenant les labels des régions de l'image, appellée ``region map''. Cette structure peut être utilisée pour filtrer un motif dans le cadre de la reconnaissance de symboles par exemple.

      % Insertion image: topo.jpg

      Pour un haut niveau d'abstraction, il existe les structures relationnelles, qui consistent à lier plusieurs données entre elles afin de représenter une image. Ce type de structure s'inspire grandement des bases de données relationnelles. La structure permet de lier entre elles les parties sémantiques de l'image. Ce type de structure est envisage dans la plupart des cas après avoir segmenter notre image de départ en plusieurs objets distincts.


      En ce qui concerne les structures hiérarchiques de données, on distingue tout d'abord les pyramides, qui se décomposent elles mêmes en deux types: les M-pyramides (à base de matrices) et les T-pyramides (à base d'arbres). Les pyramides sont composées d'une séquence d'images de différentes résolutions. Cette propriété rend donc les pyramides très pratique pour une utilisation en parallèle.

      L'autre structure arborescente est l'arbre quaternaire (ou quadTree). C'est une structure dérivée des pyramides. D'ailleurs l'année dernière dans le cadre du partitionnement de l'espace 3D, nous avions fait appel à un octree, qui n'est autre que la généralisation des quadtree à l'espace. Pour revenir aux arbres quaternaires, leur principe est que l'image à représenter est soit une image de couleur uniforme, soit la réunion de quatre sous-images carrées de mêmes tailles. Cette structure est comme son nom l'indique une structure arborescente où les feuilles contiennent les couleurs des sous-images. Les arbres quaternaires sont utilisés entre autres pour la compression d'images, en effet ils permettent de minimiser l'information nécessaire pour coder des zones homogènes. Cependant, l'ensemble des images pour lesquelles la compression par quadtree est efficace, est restreint.


    % section structures_de_donn'ees_images (end)

	% chapter repr'esentation_des_images (end)


	\chapter{Analyse de l'image et extraction} % (fold)
	\label{cha:analyse_de_l'image_et_extraction}

    \section{D\'etection des lignes} % (fold)
    \label{sec:d'etection_des_lignes}

      Après le prétraitement de l'image, on obtient une image ``parfaite'', à savoir redressée, débruitée et seuillée. C'est ensuite à la partie extraction de mettre en place la détection des lignes de l'image et l'extraction des caractères afin de pouvoir donner à la partie reconnaissance les caractères isolés. La partie extraction est également responsable de la détection des blocs dans l'image, tels que des blocs de texte, des schémas, des images ou encore des tableaux.
      Cette partie ``analyse de l'image et extraction'' se déroulera dans l'ordre suivant: tout d'abord, nous devrons détecter les blocs de l'image afin de pouvoir effectuer le traitement adéquate selon le type de bloc. En ce qui concerne le traitement des blocs de texte, on effectue une détection des lignes puis une extraction des caractères et enfin on passe les caractères à la partie ``Reconnaissance des caractères''.

      Pour cette soutenance, nous avons réalisé la détection des lignes conformément au planning. Cette détection des lignes se concrètise en un exécutable nommé \verb!extract! dans le répertoire \verb!/extraction! du projet. Il dispose de plusieurs options comme l'aide \verb!-h!, l'attribution du nom de fichier d'entrée \verb!-i [file]! et celui de sortie \verb!-o [file]!. Cette exécutable prend en entrée une image bitmap noire et blanche ``parfaite'' et génère un fichier bitmap fidèle au fichier original tout en ayant préalablement encadr\'e les lignes détectées.
      Le traitement appliqué à l'image se décompose en cinq parties. En premier lieu, l'image source est chargée dans une surface à l'aide de la librairie SDL. D'après cette surface, nous créons une matrice binaire représentant l'image. Nous effectuons ensuite la projection horizontale de cette matrice.
      La projection horizontale consiste à calculer le nombre de pixels noirs sur chaque ligne. On obtient ainsi un vecteur de projection, à savoir l'histogramme de projection horizontale de longueur la hauteur de l'image.

      Ensuite, la détection des lignes consiste à parcourir le vecteur de projection horizontale à la recherche des plages blanches (où il y a peu de pixels noirs) représentant les interlignes ainsi que les plages noires, à savoir les lignes de texte.

      Cependant appliqué tel quel, cet algorithme est peu robuste face aux pixels parasites (i.e. des tâches). En effet, ces pixels parasites auraient la fâcheuse tendance à être pris pour des lignes à part entière. C'est pourquoi lors de la détection des lignes, nous devons vérifier que les lignes détectées sont d'une hauteur suffisante. C'est pourquoi nous avons utilisé un certain seuil pour considérer une plage de pixels en tant que ligne. Afin que ce seuil soit le plus adapté, nous l'avons fixé à $10$ pixels pour une résolution de $300$ Points par Pouce. Les lignes détectées sont stockées dans une liste chainée de structure \verb!s_line_set! définie comme ceci:

      \begin{verbatim}
        struct s_line_set
        {
          int id;
          int pos;
          int height;
          struct s_character_set *charlist;
          struct s_line_set *next;
        };
      \end{verbatim}

      Cette structure est composé de plusieurs caractéristiques de la ligne, notamment sa position et sa hauteur qui nous permettent de la localiser dans l'image de départ.
      Une fois le résultat obtenu, nous générons une image présentant les lignes détéctées dans des cadres et enfin nous sauvegardons le fichier bitmap. Ces deux opérations ne nous seront utiles seulement dans le cadre de la présentation de la détection des lignes lors de la soutenance. En effet, la génération d'un fichier preview ne nous sera pas utiles dans la suite du projet.

    % section d'etection_des_lignes (end)

    \section{M\'ethodes de segmentation} % (fold)
    \label{sec:m'ethodes_de_segmentation}
      La segmentation permet de décomposer une image en plusieurs sous-images, que l'on appellera blocs. Chacun de ces blocs possédera ces propres caractèristiques, notamment ses coordonnées, sa taille ainsi que son type: texte, image ou graphique. Plusieurs méthodes de segmentation existent. Comme la segmentation est sensible au bruit, son traitement se fera à partir d'une image parfaite.
      \subsection{Segmentation par seuillage}
      La plus simple et la plus rapide est la segmentation par seuillage (threshold segmentation), qui permet de distinguer les objets de l'arrière plan. Plusieurs variantes existent, notamment la segmentation par seuillage global, semi-global et local ainsi que par multi-seuillages.
      
      % subsection segmentation_par_seuillage (end)
      
      \subsection{Segmentation par contours}
      Il y a également la segmentation par contours (edge-based segmentation) qui est utilisée pour détecter les bords des objets contenus dans des images représentant des cartes ou des photos par exemple.
      
      % subsection segmentation_par_contours (end)
      
      \subsection{Segmentation par régions}
      On distingue aussi la segmentation par régions (region-based segmentation). Ce type de segmentation consiste à créer des régions composées de pixels similaires. Ce critère de similarité est important car c'est celui-ci qui détermine le résultat obtenu après la segmentation. La segmentation par régions génére donc un ensemble de régions dontles propriétés sont:
      \begin{itemize}
        \item la réunion de toutes les régions compose l'image d'origine.
        \item toutes les régions sont connexes.
        \item les pixels d'une même région sont homogènes.
        \item les pixels de deux régions adjacentes ne sont pas homogènes.
      \end{itemize}
      
      Le critère de similarité est essentiel. Dans la plupart des cas, il consiste à définir des pixels comme similaires de part leur degré de voisinnage. On distingue deux méthodes pour créer les régions: la décomposition/fusion (Split/Merge) et la croissance de régions (growing-region).
      
      \subsubsection{Décomposition/fusion}
        Comme son nom l'indique, cette technique est composée de deux phases:
        \begin{enumerate}
          \item Décomposition: découpage itératif de l'image jusqu'à ce que l'on obtienne des blocs contenant seulement des pixels similaires.
          \item Fusion: regroupement des blocs voisins dans le cas où ils sont similaires.
        \end{enumerate}
        
        La décomposition (split) consiste à découper notre image dichotomiquement par blocs. On part d'un bloc correspondant à l'image d'origine. On étudie ensuite son contenu. Dans le cas où les données sont homogènes alors on stoppe la décomposition sinon on découpe ce bloc en 4 sous-blocs et étudie chacun de ces sous-blocs et ainsi de suite. Cette technique est implémentable selon plusieurs méthodes. On peut naturellement utilisé un arbre quaternaire pour représenter l'image, où chaque bloc serait une feuille de l'arbre. Cependant, les arbres quaternaires ne sont pas pratiques pour naviguer entre des blocs voisins. C'est pourquoi on pourrait dans ce cas utiliser une structure topologique, comme un graphe d'adjacence.
        La fusion (merge), quant à elle, se charge de regrouper les blocs entre eux selon un critère de similarité, par exemple la valeur moyenne de l'ensemble des pixels d'un bloc. Elle permet donc d'identifier les différentes régions de l'image selon un critère particulier.
      
      % Insertion image: decomposition.jpg
      
      % subsubsection decomposition_fusion
      
      \subsubsection{Croissance de régions}
      Cette autre techniaue consiste a faire grossir progressivement les regions autour de leur point de depart. 
        \begin{enumerate}
          \item Recherche des points depart.
          \item Formation des regions par agglutinement de pixels voisins.
        \end{enumerate}

        Les points de depart constitue l'un des points les plus importants de cette technique. En effet, il faut les choisir dans des zomes homogenes pour eviter aue la mesure de similarite ne provoque de fortes variations.
      % subsubsection croissance_de_régions
        Nous ne preferons pas developper ici l'implementation de ces methodes aui seront vus plus en detail pour la soutenance prochaine.
      
      % segmentation_par_regions (end)
      
    % section m'ethodes_de_s\'egmentation (end)

	% chapter analyse_de_l'image_et_extraction (end)

  % A VERIFIER (wavs)

	\chapter{Pr\'etraitement} % (fold)
	\label{cha:pr'etraitement}
		%%%%%%%%%%%%%%%%%%%%%% PIERRE
        \section{Chargement des images} % (fold)
        Pour la première soutenance, nous avons hesité entre l'utilisation des bibliothèques OcamlSdl et Camlimages, tout deux étant
        capable de charger un bon nombre de format d'images différents. Camlimages fournit une multitude de fonctions de traitement
        d'images, OcamlSdl quand a lui permet un accés relativement facile aux données de l'image --en effet la representation sous
        forme de tableau d'entiers n'est pas tres intuitive-- et une exportation au format windows BMP aisé.
        Il s'est avéré qu'il était plus facile d'utiliser les bibliotheques fournies par le PIE. Notre choix s'est donc porté vers
        la bibliothèque OcamlSdl.
        Dans tout les cas notre programme, prend n'importe quel format d'images supporté par OcamlSdl -- png, jpeg, bmp \ldots--
        et renvoie une image au format windows BMP en noir et blanc. La valeur de seuil peut etre passé en paramètre.

        \label{sec:Ocamlsdl}
        Nous sommes partis d'un fichier caml contenant l'initialisation de sdl et l'affichage d'une fenêtre. Il a fallut assimiler
        l'utilisation de cette bibliotheque, l'utilisation d'objet de type Sdlvideo.Surface en est un exemple. Pour faire ce que
        nous avons à faire nous procédons de la manière suivante:
        \begin{enumerate}
          \item On créer un objet de type \verb!Sdlvideo.surface! par l'intermédiaire du module Sdlloader qui permet de charger des
            images d'extension variées.
          \item On transforme cette objet en un tableau d'entiers grâce à des fonctions de notre cru. Mais surtout grâce a \verb!get_pixel! du module \verb!Sdlvideo!.
          \item On applique alors une fonction de seuillage, de rotation, ou de reduction du bruit (filtre médiant)
        \end{enumerate}

        Nous devons cependant signaler, que la transformation en tableau d'entier provoque un étrange phénomène au niveau des
        couleurs -- les valeurs de rouges et de bleus sont échangées --. Ce problème devra être résolue afin de sauvegarder
        les images en couleurs lors de la partie segmentation, detection des blocs. Rappelons que les fichier png ont de
        nombreux modes de gestion de la couleur ce qui pourrait expliquer deux trois phénomènes.

        \section{OCRed}
        \subsection{caml}
         Nous utilisons plusieurs outils qui nous facilitent la vie, tout d'abord Ocamlfind qui permet de trouver les bibliothéques à notre place, ce qui est fort utile. Ocamldebug malgré son étrangeté nous a permis de résoudre quelques petits problèmes.
         Nous avons organisé notre arborescence de façon clair, afin en autre de créer une documentation lisible dans le futur grâce à Ocamldoc qui permet la création d'une documentation lisible au format .info html et autre.
         Nous avons des modules dédiés à chaque tache, formules de rotation, valeurs par référence qui permettent des options d'exécution viables,transformation de l'image en type de donnée manipulable, gestion des événements utilisateur pour la partie graphique en sdl, gestion des options d'exécution grâce au module Arg de caml.
         Bref, quelquechose de comprehensible.
        \subsection{executable}
        Nous avons fait en sorte, grâce au module Arg entre autres que notre exécutable puisse fonctionner en ligne de commande pure, mais aussi avec une interface graphique en sdl. Cela permet de larges possibilitées d'utilisation, et une flexibilité importante.
        De plus les options d'exécution permettent une grande interaction avec le programme. On utilise l'option \!verb-d! qui permet de passer en mode graphique et donc de visualiser immédiatement les modifications efféctuées sur l'image.
        \section{Rotation de l'image}
        \label{principe}
        La rotation d'une image ce fait par rapport à son centre, nous devons donc prendre en compte le décalage.
        Il faut aussi remarquer qu'une rotation d'un angle différent de $O mod \pi$ nous donne une position des
        pixels de destinations qui dépasse les bornes du tableau source. De ce fait notre image
        de sortie sera plus grande. A l'avenir les images seront plus petites, on devra pour cela determiner les valeurs réelles
        des bornes du fichier source.
        La rotation d'une image pose d'autres problèmes que ceux citées plus haut:
        \begin{enumerate}
          \item la formule trigonométrique habituelle pour la rotation retourne des valeurs flottantes. On se retrouve donc avec des pixels qui en chevauchent plusieurs autre.
          \item nous avons donc des pertes de données importantes, la solution envisagée serait une interpolation bilinéaire
        \end{enumerate}
        Ansi la rotation peut être mise en équation de la façon suivante :
%%%%%%%%%%%%%%%%%%%%%%%%%FIXME
%%%%%%%%%%%%%%%%%%%%%%%% mettre les equations
        %%                                ∀( x', y') ∈ dst ∃( x , y ) ∈ R2
        %       tel que :
        %                              x'    = x · cos (−α) − y · sin (−α)
        %
        %                              y'    = x · sin (−α) + y · cos (−α)
        %
        %       On a donc :
        %                         si ( x , y ) ∈ tableausource
        %                                 valeur de (x',y') = valeur de (x,y)
        %                         sinon
        %                                 valeur de (x',y') = 255 ou 0 (blanc ou noir) celon ce que l'on veut

	% chapter pr'etraitement (end)


	\chapter{R\'eseau de neurones} % (fold)
	\label{cha:r'eseau_de_neurones}

		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
		%%%%%%%%%%%%%%%%%%%%%% FIXME
		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
		%%%%%%%%%%%%%%%%%%%%%% DIMITRI
		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	% chapter r'eseau_de_neurones (end)


	\chapter{Interface graphique} % (fold)
	\label{cha:interface_graphique}
		\section{Pourquoi une interface?} % (fold)
		\label{sec:pourquoi_une_interface_}
		C'est vrai \c ca, est-ce que c'est vraiment utile? Sachant que notre programme n'effectuera qu'une action principale (trouver du texte dans une image), pourquoi s'emb\^eter \`a d\'evelopper une interface graphique? Parce que. Parce que les gens normaux utilisent une souris depuis 1984, et qu'ils veulent cliquer sur un bouton et non pas tapper une commande, aussi simple soit elle.
		
		L'interface est un aspect primordial dans un logiciel. Chaque bouton doit \^etre \`a sa place. \'Enorm\'ement de logiciels n'ont pas re\c cu les \'eloges qu'ils m\'eritent \`a cause d'une interface bacl\'ee. L'utilisateur doit trouver ce qu'il cherche tr\`es rapidement. Il doit y avoir le moins de boutons possible tout en offrant une large palette d'options. Pas si simple\ldots
		
		L'une des r\'ef\'erences en mati\`ere d'ergonomie est bien entendu le syst\`eme Mac OS X. Nous avons donc parcouru les \emph{Apple Human Interface Guidelines}\footnote{$http://developer.apple.com/documentation/UserExperience/Conceptual/OSXHIGuidelines/$}, un document de 400 pages qui s'est r\'ev\'el\'e \^etre tr\`es int\'eressant. Parmi les conseils les plus utiles, certains peuvent para\^itre \'evident mais il est affligeant de voir que tant d'applications ne respectent pas ces principes de bases. Nous nous efforcerons donc dans la limite du possible de respecter quelques r\`egles de bases, comme offrir des options par d\'efaut qui conviendront \`a l'utilisateur lambda (pas aux \emph{geeks} que nous sommes), ou encore n'ajouter des fonctions que si elles satisfont au moins $80\%$ des utilisateurs, et non pas les $20\%$ de \emph{power users}.
		
		
		% section pourquoi_une_interface_ (end)
		\section{Gtkoi?} % (fold)
		\label{sec:gtkoi_}
			Le cahier des charges nous impose une interface utilisant la biblioth\`eque Gtk. On a donc commenc\'e par se documenter l\`a-dessus.\\
			Gtk signifie ``The GIMP Toolkit'', puisque Gtk a \'et\'e cr\'e\'e pour le logiciel de traitement d'images ``The GIMP''. C'est en fait un ensemble de biblioth\`eques utilis\'e pour r\'ealiser des interfaces graphiques. Et \c ca n'avait pas l'air simple \`a utiliser.\\
			Heureusement, nous avons rapidement d\'ecouvert qu'il existe un outil qui va nous faciliter la vie. Il se nomme Glade. C'est un outil qui simplifie grandement la cr\'eation de l'interface pour nous permettre de nous concentrer sur le code ``pur''. Glade 3 fonctionne tr\`es bien sur les machines du PIE. Il a le m\'erite de nous offrir une interface assez intuitive, je l'ai donc pris en main tr\`es rapidement.\\
			Nous cr\'eons donc une interface en utilisant Glade puis nous relions chaque ``signal'' dans un \texttt{.c}. Les ``signals'' sont des sortes d'``\'ev\`enement'' auquel on peut relier une action en utilisant Gtk.\\
			Pour relier un signal \`a une action, on utilise la fonction suivante:

			\begin{verbatim}
				glade_xml_signal_connect (gxml, "on_window_destroy",
							    G_CALLBACK (gtk_main_quit));
			\end{verbatim}

			Ici, \verb!gxml! est notre fichier xml, \verb!"on_window_destroy"! est le signal auquel on rattache la fonction Gtk \verb!gtk_main_quit! qui quitte l'application en cours. Cette simple ligne de code nous permet de signifier au programme que lorsqu'on clique sur la ``croix'' en haut \`a droite de notre fen\^etre, il faut non seulement fermer la fen\^etre mais aussi l'application.
			On peut bien entendu lui sp\'ecifier d'autres fonctions que celles de Gtk.

		% section gtkoi_ (end)

		\section{Ce qu'on a fait} % (fold)
		\label{sec:ce_qu_on_a_fait}
			Pour cette soutenance, nous somme pri\'e de bien vouloir rendre une \'ebauche d'interface. C'est donc une interface assez incompl\`ete que l'on rend. Pour l'instant, notre interface ne sait faire qu'une chose: ouvrir une image! Une fonction e\'l\'ementaire qui ne s'est pas r\'ev\'el\'ee \^etre si simple que \c ca \`a d\'evelopper. Notre fen\^etre est divis\'ee en trois:
			\begin{enumerate}
				\item Une barre d'outil qui contiendra les raccourcis vers les fonctionalit\'es de base,
				\item La partie gauche de la fen\^etre affichera l'image scann\'ee,
				\item La partie droit contiendra le texte obtenu \`a partir de l'image que l'utilisateur pourra modifier puis enregistrer.
			\end{enumerate}
			
			Nous avons aussi ajout\'e une petite bo\^ite d'``A propos'', visible en cliquant sur ``Help > About''. 
		% section ce_qu_on_a_fait (end)
		
		
		
	% chapter interface_graphique (end)

	\chapter{Site Web} % (fold)
	\label{cha:site_web}
		\section{Ce qu'on veut} % (fold)
		\label{sec:ce_qu_on_veut}
		Le site web\footnote{\emph{http://huge.ocre.free.fr}} est la premi\`ere chose que verra l'utilisateur potentiel. Il devra donc \^etre \`a la fois attirant et bien ordonn\'e. Le site devra comporter:
		\begin{itemize}
			\item Une page d'accueil qui expliquera bri\`evement ce qu'est notre projet, qui nous sommes, etc\ldots
			\item Une page de d\'eveloppement qui informera le visiteur des avanc\'ees du projet. Il contiendra aussi un lien vers notre page Google Code.
			\item Une page de t\'el\'echargement qui listera chronologiquement tout ce qu'on a cr\'e\'e, c'est \`a dire nos sources, les \'ex\'ecutables et les rapports de soutenances.
			\item Une page de liens,
			\item Une page d'``A propos'' qui expliquera plus en d\'etail qui nous sommes, ce qu'est l'Epita, etc\ldots
		\end{itemize}
		De plus, nous aimerions bien avoir un site enti\`erement bilingue (anglais/fran\c cais)
		% section ce_qu_on_veut (end)
		\section{Comment on s'est d\'ebrouill\'e} % (fold)
		\label{sec:comment_on_s_est_d'ebrouill'e}
		Comment on s'est débrouillé

			On est parti avec l'idée que le site web ne devrait pas nous éloigner de notre tâche principale: développer un logiciel de reconnaissance de caractères. Le site web est donc tr\`es basique. Nous avons 10 pages HTML, 5 en anglais et 5 en fran\c cais. Chaque page est reli\'ee \`a sa traduction dans l'autre langue.
			Le code HTML de chaque page ne fait que quelques lignes, nous avons plus mis l'accent sur le fichier CSS. Les balises \verb!<div id="">! correspondent \`a un style du fichier CSS. Ce fichier nous autorise \`a d\'efinir la position des \'el\'ement ain si que divers effets qui se r\'ev\`elent assez utiles pour par exemple personaliser les liens.
			La page d'accueil est visible en annexe.
			 

		% section comment_on_s_est_d'ebrouill'e (end)
	% chapter site_web (end)
% part ce_qu_on_a_fait (end)



\part{Ce qu'on compte faire} % (fold)
\label{prt:ce_qu_on_compte_faire}

\chapter{Pr\'etraitement de l'image} % (fold)
        \section{angle de rotation et optimisation}
        Nous avons r\'eussi a appliquer une rotation sur une image, il faut cependant remarquer que cette rotation peut \^etre optimiser, notament en \'evitant les cas triviaux tels que la rotation d'angle 90 degr\'e, en r\'eduisant la taille de l'image de sortie, mais aussi en applicant une interpolation bi-lin\'eaire qui permettra d'\'eviter de fa\c con intelligente une perte trop violente d'information.
        La detection de l'angle de rotation devra \^etre viable pour la deuxi\'eme soutenance, cela implique que nous implementions les divers algos et principes d\'ecouverts au cour de nos intenses recherches.
        \section{reduction du bruit}
        Nous utilisons un filtre m\'edian, utile pour la suppresion du bruit de type point. Il existe cependant de nombreux autres types de filtres efficaces sur ce type de bruit mais aussi sur d'autres. Nos fonctions de filtrages sont assez ``moche'' au niveau de l'optimisation. Nous avons deja les algos pour l'optimisation du filtre m\'edian. Il faudra aussi penser a fournir d'autre filtres, qui permettront un niveau d'utilisation du programme plus large. Et bien sur il faudra les impl\'ementer.

\chapter{Analyse de l'image et extraction} % (fold)
\label{cha:analyse_de_l'image_et_extraction}

    \section{D\'etection des caractères} % (fold)
    \label{sec:d'etection_des_caractères}
      Pour les prochaînes soutenances, nous devrons réaliser une détection des caractères fonctionnelle qui sera robuste vis-à-vis des pixels parasites, du chevauchement des caractères et du défaut d'encrage excessif ou insuffisant. Pour cela, on utilisera vraisemblablement la projection verticale des pixels pour chaque ligne détectée. Pour le problème des pixels parasites, on incluera un seuil. En ce qui concerne le  chevauchement de caractères, on devra vérifier que les transitions entre l'arrière plan et les caractères ainsi que la connexité possible entre deux caractères, nous serons vraisemblablement ammené à utiliser une représentation topologique tel qu'un graphe. Pour les éventuelles problèmes d'encrage insuffisant, nous ferons appel à un autre seuil minimum de largeur de caractère. Enfin dans le cas d'un encrage excessif, on utilisera l'algorithme dit du ``Break Cost''.

    % section d'etection_des_caractères (end)

    \section{Segmentation} % (fold)
    \label{sec:s\'egmentation}
  		Nous devrons implémenter une méthode de détection de bloc afin de pouvoir différencier les blocs de texte à ceux d'images ou de graphiques. Comme énoncé dans précédemment, plusieurs méthodes s'offrent à nous pour effectuer ce traitement. Nous devrons également trouvé une structure de données permettant de stocker ces différents blocs et leurs caractéristiques propres mais également une structure permettant de garder en mémoire les propriétés du texte, à savoir les paragraphes ou encore les tabulations.

    % section s\'egmentation (end)

	% chapter analyse_de_l'image_et_extraction (end)

% part ce_qu_on_compte_faire (end)

\chapter{Conclusion}
Ce qu'on a d\'evelopp\'e jusqu'\`a pr\'esent n'a pas grand chose \`a voir avec un OCR. Pourtant, nous ne sommes pas m\'econtent de ce que nous avons accompli. Nous avons fait ce qui \'etait demand\'e (et parfois m\^eme un peu plus), en codant de fa\c con bien plus ``mature'' que l'ann\'ee derni\`ere (merci la norme impos\'ee).
Le plus important \`a nos yeux c'est d'avoir retrouv\'e le plaisir de coder tous ensemble autour d'une cafeti\`ere et d'une multiprise. Nous avons retrouv\'e cet esprit d'\'equipe que nous avions l'ann\'ee derni\`ere. On n'ose m\^eme pas imaginer \`a quel point cela doit \^etre difficile de coder au sein d'un groupe qui ne s'entend pas.



\appendix

\section{Site} % (fold)
\label{sec:site}
	\includegraphics[width=150mm]{screen_site.png}
  
% section site (end)

\bibliographystyle{plain}
\bibliography{}
\end{document}
